package common

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func BuildTree(nums []any) *TreeNode {
	if len(nums) == 0 {
		return nil
	}

	var nodes = make([]*TreeNode, 0, len(nums))
	for _, num := range nums {
		if num == nil {
			nodes = append(nodes, nil)
		} else {
			node := &TreeNode{Val: num.(int)}
			nodes = append(nodes, node)
		}
	}

	var level = 0 // 层级，从0开始
	var stop = false
	var curIndex = 0

	for !stop {
		var levelCount = 1 << level            // 当前层级有多少节点
		var childIndex = curIndex + levelCount // 子节点的下标

		// 处理一整层的节点，把子节点挂到父节点
		for i := 0; i < levelCount && !stop; i, curIndex = i+1, curIndex+1 {
			if nodes[curIndex] == nil {
				childIndex += 2
				continue
			}

			if childIndex >= len(nodes) {
				stop = true
				break
			}

			nodes[curIndex].Left = nodes[childIndex]
			childIndex++
			if childIndex >= len(nodes) {
				stop = true
				break
			}

			nodes[curIndex].Right = nodes[childIndex]
			childIndex++
		}

		level++
	}

	return nodes[0]
}

func GetDeep(root *TreeNode) int {
	if root == nil {
		return 0
	}

	left := GetDeep(root.Left)
	right := GetDeep(root.Right)
	if left > right {
		return left + 1
	}
	return right + 1
}

// InorderTraversal 二叉树中序遍历   左-> 根-> 右
func InorderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}
	inorderTraversal(root, &result)
	return result
}

func inorderTraversal(root *TreeNode, result *[]int) {
	if root == nil {
		return
	}
	if root.Left != nil {
		inorderTraversal(root.Left, result)
	}
	*result = append(*result, root.Val)
	if root.Right != nil {
		inorderTraversal(root.Right, result)
	}
}
